In mathematics,

computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

telecommunication Telecommunication is the transmission of information by various types of technologies over wire, radio, optical, or other electromagnetic systems. It has its origin in the desire of humans for communication over a distance greater than that fe ...

, information theory, and searching theory, error-correcting codes with feedback refers to

error correcting codes In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...

designed to work in the presence of feedback from the receiver to the sender.See and .

Problem

Alice (the sender) wishes to send a value ''x'' to Bob (the receiver). The communication channel between Alice and Bob is imperfect, and can introduce errors.

Solution

An error-correcting code is a way of

encoding In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication ...

''x'' as a message such that Bob will successfully understand the value ''x'' as intended by Alice, even if the message Alice sends and the message Bob receives differ. In an error-correcting code with feedback, the channel is

two-way Two-way or Two Way may refer to: * " 2-Way", single by rapper Lil' Romeo * Two-way, Cincinnati chili topped on spaghetti * "Two Way" (KT Tunstall and James Bay duet), 2016 See also * * * * 3-Way (disambiguation) {{Disambiguation ...

: Bob can send feedback to Alice about the message he received.

Noisy feedback

In an error-correcting code without noisy feedback, the feedback received by the sender is always free of errors. In an error-correcting code with noisy feedback, errors can occur in the feedback, as well as in the message. An error-correcting code with noiseless feedback is equivalent to an

adaptive Adaptation, in biology, is the process or trait by which organisms or population better match their environment Adaptation may also refer to: Arts * Adaptation (arts), a transfer of a work of art from one medium to another ** Film adaptation, a ...

search strategy with errors.See and .

History

In 1956,

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, and cryptographer known as a "father of information theory". As a 21-year-old master's degree student at the Massachusetts Inst ...

introduced the

discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a g ...

memoryless In probability and statistics, memorylessness is a property of certain probability distributions. It usually refers to the cases when the distribution of a "waiting time" until a certain event does not depend on how much time has elapsed already ...

channel with noiseless feedback. In 1961, Alfréd Rényi introduced the

Bar-Kochba game Simon ben Koseba or Cosiba ( he, שִׁמְעוֹן בַּר כֹסֵבָא, translit= Šīmʾōn bar Ḵōsēḇaʾ‎ ; died 135 CE), commonly known as Bar Kokhba ( he, שִׁמְעוֹן בַּר כּוֹכְבָא‎, translit=Šīmʾōn bar ...

(also known as Twenty questions), with a given percentage of wrong answers, and calculated the minimum number of randomly chosen questions to determine the answer. In his 1964 dissertation,

Elwyn Berlekamp Elwyn Ralph Berlekamp (September 6, 1940 – April 9, 2019) was a professor of mathematics and computer science at the University of California, Berkeley.Contributors, ''IEEE Transactions on Information Theory'' 42, #3 (May 1996), p. 1048. DO10. ...

considered error correcting codes with noiseless feedback.. In Berlekamp's scenario, the receiver chose a subset of possible messages and asked the sender whether the given message was in this subset, a 'yes' or 'no' answer. Based on this answer, the receiver then chose a new subset and repeated the process. The game is further complicated due to noise; some of the answers will be wrong.

Sources

* . * .

References

{{reflist